522D - Closest Equals - CodeForces Solution

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
using namespace std;
long long n, m;
vector<long long> v1, v2, v3, tree;
map<long long, long long> mp;
void build(long long v, long long l, long long r) {
    if (l == r) {
        tree[v] = v2[l];
        return;
    }
    long long m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
}
long long get(long long v, long long l, long long r, long long ln, long long rn) {
    if (l >= ln && r <= rn)
        return tree[v];
    if (l > rn || r < ln)
        return 1e18;
    long long m = (l + r) / 2;
    return min(get(v * 2, l, m, ln, rn), get(v * 2 + 1, m + 1, r, ln, rn));
}
void update(long long v, long long l, long long r, long long i) {
    if (r < i || l > i)
        return;
    if (l == r) {
        tree[v] = 1e18;
        return;
    }
    long long m = (l + r) / 2;
    update(v * 2, l, m, i);
    update(v * 2 + 1, m + 1, r, i);
    tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    v1.resize(n);
    v2.resize(n, 1e18);
    v3.resize(n, -1);
    tree.resize(4 * n);
    for (long long i = 0; i < n; i++) {
        cin >> v1[i];
        mp[v1[i]] = -1;
    }
    for (long long i = 0; i < n; i++) {
        if (mp[v1[i]] != -1) {
            v3[mp[v1[i]]] = i;
            v2[i] = i - mp[v1[i]];
        }
        mp[v1[i]] = i;
    }
    build(1, 0, n - 1);
    vector<pair<pair<long long, long long>, long long>> zap(m);
    vector<long long> ans(m);
    for (long long i = 0; i < m; i++) {
        cin >> zap[i].first.first >> zap[i].first.second;
        zap[i].first.first--;
        zap[i].first.second--;
        zap[i].second = i;
    }
    sort(zap.begin(), zap.end());
    long long x3 = 0;
    for (long long i = 0; i < n; i++) {
        while (x3 < m && zap[x3].first.first == i) {
            ans[zap[x3].second] = get(1, 0, n - 1, i, zap[x3].first.second);
            if (ans[zap[x3].second] == 1e18)
                ans[zap[x3].second] = -1;
            x3++;
        }
        if (v3[i] == -1)
            continue;
        update(1, 0, n - 1, v3[i]);
    }
    for (long long i = 0; i < m; i++)
        cout << ans[i] << "\n";
    return 0;
}

/* Wed Jul 05 2023 13:58:14 GMT+0300 (Moscow Standard Time) */

/* Wed Jul 05 2023 13:58:20 GMT+0300 (Moscow Standard Time) */